package 算法.线性表;


import java.util.Scanner;
import java.util.Stack;

/***
 *  计算器
 *  中缀式转后缀式：
 *      1.从左至右依次扫描字符串
 *      2.遇到数子直接入栈（1）
 *      3.遇到操作符：
 *          1）若当前操作符为（ ，则直接入栈
 *          2）若当前操作符为 ），则依次弹出操作符栈压入数栈，至栈顶为（ ，并抛弃（。
 *          3）判断操作符栈是否为空、或者栈顶元素的优先级是否大于当前操作符，
 *              是则继续压栈；
 *              否则将栈顶弹出压入数字栈，并重复该步骤。
 *      4.扫描至字符串尾部，并将操作符栈依次弹出压入数字栈。
 *      5.数字栈逆序即为后缀式。
 */

public class 中缀式转后缀式 {
    public static void main(String[] args) {
        Stack<String> stack1 = new Stack<>();
        Stack<String> stack2 = new Stack<>();
        Scanner in = new Scanner(System.in);
        char[] str = in.nextLine().toCharArray();
        //1.从左至右依次扫描字符串
        for (int i = 0; i < str.length; i++) {
            //2.遇到数子直接入栈（1）
            if (str[i] >= '0' && str[i] <= '9') {
                String temp = String.valueOf(str[i]);
                while (i + 1 < str.length && str[i + 1] != '=' && str[i + 1] != '+' && str[i + 1] != '-' && str[i + 1] != '*' && str[i + 1] != '/' && str[i + 1] != '(' && str[i + 1] != ')') {
                    temp += str[++i];
                }
                stack1.push(temp);
            }
            // 3.遇到操作符：
            else{
                //1）若当前操作符为（ ，则直接入栈
                if (str[i] == '(')
                    stack2.push(String.valueOf(str[i]));
                // 2）若当前操作符为 ），则依次弹出操作符栈压入数栈，至栈顶为（ ，并抛弃（。
                else if (str[i] == ')') {
                    while (true){
                    String temp = stack2.pop();
                    if (temp.equals("("))
                        break;
                    else
                        stack1.push(temp);
                    }
                }
                else if (str[i] == '=')
                    continue;
                else {
                    // 3）判断操作符栈是否为空、或者栈顶元素的优先级是否大于当前操作符，
                    //       是则继续压栈；
                    //       否则将栈顶弹出压入数字栈，并重复该步骤。
                    while (true) {
                        if (stack2.empty()||stack2.peek().equals("(")||priority(str[i], stack2.peek())){
                            stack2.push(String.valueOf(str[i]));
                            break;
                        }
                        else
                            stack1.push(stack2.pop());
                    }
                }
            }
        }
        //4.扫描至字符串尾部，并将操作符栈依次弹出压入数字栈。
        while (!stack2.empty())
            stack1.push(stack2.pop());
        //5.数字栈逆序即为后缀式。
        while (!stack1.empty())
            stack2.push(stack1.pop());
        System.out.print("后缀式：");
        while (!stack2.empty())
            System.out.print(stack2.pop()+" ");
    }

    private static boolean priority(char c, String s) {
        if ((c == '*' || c == '/') && (s.equals("-") || s.equals("+")))
            return true;
        else
            return false;

    }
}


